#pragma once
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include<utility>

//binary tree node
template<class T>
struct binaryTreeNode
{
	T element;
	binaryTreeNode<T>* leftChild;
	binaryTreeNode<T>* rightChild;

	binaryTreeNode() { leftChild = rightChild = nullptr; }
	binaryTreeNode(T theElement):element(theElement){}
	binaryTreeNode(T theElement, binaryTreeNode* theLeftChild, binaryTreeNode* theRightChild)
		:element(theElement), leftChild(theLeftChild), rightChild(theRightChild){}
};

//binary tree abstract class
template<class T>
class binaryTree
{
public:
	virtual ~binaryTree(){}
	virtual bool empty() const = 0;
	virtual int size() const = 0;
	virtual void preOrder(void (*) (T *)) = 0;
	virtual void inOrder(void (*) (T *)) = 0;
	virtual void postOrder(void (*) (T *)) = 0;
	virtual void levelOrder(void (*) (T *)) = 0;
};

//linked list binary tree
template<class K>
class linkedBinaryTree :public binaryTree<binaryTreeNode<K>>
{
public:
	linkedBinaryTree() { root = nullptr, treeSize = 0; }
	~linkedBinaryTree() { erase(); };
	bool empty() const override { return treeSize == 0;}
	int size() const override { return treeSize; }
	void preOrder( void (*theVisit) (binaryTreeNode<K>*))
	{
		visit = theVisit;
		preOrder(root);
	}
	void inOrder(void (*theVisit) (binaryTreeNode<K>*))
	{
		visit = theVisit;
		inOrder(root);
	}
	void postOrder(void (*theVisit) (binaryTreeNode<K>*))
	{
		visit = theVisit;
		postOrder(root);
	}
	void levelOrder(void (*theVisit) (binaryTreeNode<K>*));
	void erase() 
	{ 
		postOrder(dispose);
		root = nullptr;
		treeSize = 0;
	}

public:
	binaryTreeNode<K>* root;//a pointer to the root node
	int treeSize;
	static void (*visit) (binaryTreeNode<K>*);
	static void preOrder(binaryTreeNode<K>* t);
	static void inOrder(binaryTreeNode<K>* t);
	static void postOrder(binaryTreeNode<K>* t);
	static void levelOrder(binaryTreeNode<K>* t);
	static void dispose(binaryTreeNode<K>* t) { delete t; };
};

//search binary tree
template<class K,class E>
class binarySearchTree :public linkedBinaryTree<std::pair<const K, E>>
{
public:
	std::pair<const K, E>* find(const K& theKey) const;
	void insert(const std::pair<const K, E>& thePair);
	void erase(const K& theKey);
};

#endif